This patent specification contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
The present invention relates generally to image compression technology, and in particular, to the use of transform techniques in a manner which improves the performance of the decompression process, especially for scanline and band-based systems which produce decompressed output in raster order.
Typically, data compression using wavelet techniques is, in broad terms, a two step process. This can be seen in FIG. 1, where a data block 100, undergoes a wavelet transform process 104, and a subsequent coding process 108. It is noted that transform data is segmented, and segments are coded independently. Thereafter, the coded data stream is transmitted, either over a network between disparate equipment, or over a backplane, within a single piece of equipment, as exemplified by an arrow 110, and input to a decoding process 112. The decoding process then outputs a decoded data stream 114 to an inverse wavelet transform process 116, where-after a reconstituted data block 120 is produced.
A standard decomposition process 104 for computing wavelet transforms of the input data block 100 generates sub-band data which is not spatially localized. If this data is coded by the process 108 into a data stream without any re-ordering, then the input buffer implemented at the decoder 112 must be able to store the information required to decode a particular output data point in the data block 120, the needed information being distributed in the data stream.
Turning to FIG. 2, wavelet transformation of a data block 400 is typically performed using high pass and low pass filtering operations, and also a decimation (ie. down sampling) by two, resulting, initially, in production of two output data sets i.e. the high pass and low pass sub-bands. The aforementioned process constitutes a single xe2x80x9clevelxe2x80x9d of transformation. The wavelet transform process can be multi-level, consequently storing the high pass sub-band at each level, and then recursively applying the filtering/decimation operation to the resultant low pass sub-band. Each such step produces another level, and the process continues, typically, for some predetermined number of levels, or until some cost or error function is satisfied. In FIG. 2, an input data block 400 of length 436 (i.e. xe2x80x9cuxe2x80x9d) is transformed into a data set 402 which comprises a low pass third level segment 404 (i.e. L3), a high pass third level segment 406 (i.e. H3), a high pass second level segment 408 (i.e. H2), and a high pass first level segment 410 (i.e. H1). The transformed data set 402 has the same length 436 as the input data set 400, since no data compression has been performed. Compression can be achieved by coding the transformed data set 402. In one method of coding, the transformed data set 402 is first segmented into equal sized segments of length 438 (i.e. of width xe2x80x9cwxe2x80x9d) as shown in the segmented data set 412. Additional information can also be incorporated into the data set 412, in order to identify start and end points of each segment of length 438. Thereafter, each transformed segment 414 can be independently coded to form an equivalent coded segment 418. When compression is performed, each segment 414 will xe2x80x9cshrinkxe2x80x9d in size according to the compression achieved on a per-segment basis, and thus the coded data set 416 can have a shorter length than the original data block 400, and the transformed data set 402. The issue of compression coding is not the direct focus in the present specification, and it will thus hence forth be assumed, for the sake of ease of description, that no actual compression gain is sought. It is noted that the discussion is however equally relevant if compression gain were to be provided.
The coding of the transform data set 412, under the assumption of zero compression gain, produces a coded data set 416, where each segment 418 corresponds directly to the uncoded data item 414 in data set 412.
The inverse wavelet transform requires, for each reconstituted data segment 424, constituent segments which are distributed across the data set 420. Thus, for example, data segment 424 in the inverse transformed data set 422 (this being the recovered data block equivalent to original data segment 440 in the data block 400), requires constituent data segments 426, 428, 430 and 432, i.e. one segment from each sub-band L3, H3, H2 and H1. Consequently, not only is a delay (represented by an arrow 434) incurred before the inverse transformation of the segment 424 can occur, but in addition, the data items Z1 through Z9 (see data set 416) are required to be stored (or alternatively the unneeded segments Z2, Z4, Z6-Z8 are discarded and subsequently re-transmitted as needed). Therefore, the minimum information required at the inverse transform process 116 (see FIG. 1) in order to produce the output in raster order is the coded information that corresponds to the data segments 426, 428, 430 and 432. If the compressed data stream 416 is sent in sequential order as shown in FIG. 2 without the any rearrangement or re-ordering, the inverse transform process 116 must wait until all the coded data segments through to the first segment of the H1 level 410 has been received. This extracts a penalty in both memory requirements, and latency in the decode/inverse transform processes 112, 116. The time delay, or equivalently the memory required, which is associated with the data which must be stored before the inverse transform can be applied to recover the first segment 424 is represented presented mathematically by:
(u/2)+w
where u is the span, or length of the data set 400 (ie. 436), and w is the length of the individual segment 438. This representation assumes zero compression gain.
An unordered segment stream therefore results in a penalty in memory requirements and/or in the delay suffered before a given data point in the recovered data block can be recovered.
It is an object of the present invention to substantially overcome, or at least ameliorate, one or more disadvantages of existing arrangements.
According to a first aspect of the invention, there is provided a method of selecting transform segments from a data stream, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the selection of said segments reordering the transform segments in at least one said block, the method comprising, for each said block, the steps of:
selecting a first set of transform segments suitable for direct inverse transformation to form a first data segment;
selecting a second transform segment being directly inverse transformable dependent upon the first set;
identifying a third transform segment not being directly inverse transformable dependent upon the first set and the second transform segment; and
selecting a fourth transform segment required to support direct inverse transformation of the third transform segment.
According to a second aspect of the invention, there is provided a method of ordering transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the ordering of said segments characterised in that the ordering results in a smaller set of transform segments that need to be stored, thus reducing a size of storage means in the image decoder.
According to a third aspect of the invention, there is provided a method of ordering transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the ordering of said segments characterised in that the ordering allows immediate application of an inverse discrete wavelet transform, thereby reducing a latency in the image decoder.
According to a fourth aspect of the invention, there is provided a method of ordering transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the ordering of said segments characterised in that the ordering allows raster operation of the image decoder for scanlines or bands.
According to a fifth aspect of the invention, there is provided an apparatus selecting transform segments from a data stream, the stream comprising a plurality of blocks each comprising a plurality of transform segments, the selection of said segments reordering the transform segments in at least one said block, the apparatus comprising:
first transform segment selection means adapted to select a first set of transform segments suitable for direct inverse transformation to form a first data segment;
second transform segment selection means, adapted to select a second transform segment being directly inverse transformable dependent upon the first set; and
third transform segment identification means, adapted to identify a third transform segment not being directly inverse transformable dependent upon the first set and the second transform segment; and
a fourth transform segment selection means, adapted to select a fourth transform segment required to support direct inverse transformation of the third transform segment.
According to a sixth aspect of the invention, there is provided a computer readable memory medium for storing a program for apparatus which selects transform segments from a data stream, said program comprising:
code for a first selecting step for selecting a first set of transform segments suitable for direct inverse transformation to form a first data segment;
code for a second selecting step for selecting a second transform segment being directly inverse transformable dependent upon the first set;
code for an identifying step for identifying a third transform segment not being directly inverse transformable dependent upon the first set and the second transform segment; and
code for a third selecting step for selecting a fourth transform segment required to support direct inverse transformation of the third transform segment.
According to a seventh aspect of the invention, there is provided a computer readable memory medium for storing a program for apparatus which orders transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, said program comprising code whereby the ordering of said segments is characterised in that the ordering results in a smaller set of transform segments that need to be stored, thus reducing a size of storage means in the image decoder.
According to an eighth aspect of the invention, there is provided a computer readable memory medium for storing a program for apparatus which orders transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, said program comprising code whereby ordering of said segments is characterised in that the ordering allows immediate application of an inverse discrete wavelet transform, thereby reducing a latency in the image decoder.
According to a ninth aspect of the invention, there is provided a computer readable memory medium for storing a program for apparatus which orders transform segments from a data stream for an image decoder, the stream comprising a plurality of blocks each comprising a plurality of transform segments, said program comprising code whereby ordering of said segments is characterised in that the ordering allows raster operation of the image decoder for scanlines or bands.
The present invention thus optimizes the ordering of coded segments from the coding process 108 in a manner which supports the compression in the decoder/inverse transform process (112,116), while also reducing memory requirements and delay in said processes.